package hyy_2022;

import commons.TreeNode;

/**
 * 平衡二叉树,自底向上的递归
 */
public class _0726_110_BalancedTree {

    /**
     * 判断是否为平衡二叉树
     * @param root
     * @return -1则不为平衡二叉树
     */
    public static boolean isBalanced(TreeNode root) {
        return height(root) >= 0 ;
    }

    /**
     * 求节点高度
     * 1、先计算节点左子树的高度,再计算节点右子树高度,最后计算节点高度,类似于后续遍历
     * 2、节点的高度 = 左子树高度 与 右子树高度最大值 + 1
     * 3、如果左子树高度 - 右子树高度 > 1,则证明此节点已不平衡,则整棵树都不平衡
     * 4、如节点高度>1 ,返回此节点高度为-1, 以此代表节点不平衡
     * @param root
     * @return 返回高度值
     */
    public static int height(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        if(leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        } else {
            return Math.max(leftHeight,rightHeight) + 1;
        }
    }
}
